#include <ctime>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// 递归版
void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int i = left, j = right;
    int base = i + rand() % (j - i + 1);
    swap(nums[base], nums[i]);
    while (i < j) {
        while (i <= right && nums[i] <= nums[left]) i++;
        while (nums[j] > nums[left]) j--;
        if (i < j) swap(nums[i], nums[j]);
    }
    swap(nums[left], nums[j]);
    quickSort(nums, left, j - 1);
    quickSort(nums, j + 1, right);
}



// 迭代版
int sep(vector<int>& nums, int left, int right) {
    int mid = left + rand() % (right - left + 1);
    swap(nums[left], nums[mid]);
    int i = left, j = right;
    while (i < j) {
        while (i <= right && nums[i] <= nums[left]) i++;
        while (nums[j] > nums[left]) j--;
        if (i < j) swap(nums[i], nums[j]);
    }
    swap(nums[left], nums[j]);
    return j;
}

void quickSort2(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    stack<pair<int, int>> st;
    st.push(make_pair(left, right));
    while (!st.empty()) {
        auto p = st.top();
        st.pop();
        int mid = sep(nums, p.first, p.second);
        if (mid + 1 < p.second) st.push(make_pair(mid + 1, p.second));
        if (p.first < mid - 1) st.push(make_pair(p.first, mid - 1));
    }
    return;
}
